home *** CD-ROM | disk | FTP | other *** search
/ Celestin Apprentice 2 / Apprentice-Release2.iso / Source Code / C / Libraries / Berkeley DB 1.6 / btree / bt_put.c < prev    next >
Encoding:
C/C++ Source or Header  |  1993-06-04  |  8.1 KB  |  314 lines  |  [TEXT/????]
  1. /*-
  2.  * Copyright (c) 1990, 1993
  3.  *    The Regents of the University of California.  All rights reserved.
  4.  *
  5.  * This code is derived from software contributed to Berkeley by
  6.  * Mike Olson.
  7.  *
  8.  * Redistribution and use in source and binary forms, with or without
  9.  * modification, are permitted provided that the following conditions
  10.  * are met:
  11.  * 1. Redistributions of source code must retain the above copyright
  12.  *    notice, this list of conditions and the following disclaimer.
  13.  * 2. Redistributions in binary form must reproduce the above copyright
  14.  *    notice, this list of conditions and the following disclaimer in the
  15.  *    documentation and/or other materials provided with the distribution.
  16.  * 3. All advertising materials mentioning features or use of this software
  17.  *    must display the following acknowledgement:
  18.  *    This product includes software developed by the University of
  19.  *    California, Berkeley and its contributors.
  20.  * 4. Neither the name of the University nor the names of its contributors
  21.  *    may be used to endorse or promote products derived from this software
  22.  *    without specific prior written permission.
  23.  *
  24.  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  25.  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  26.  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  27.  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  28.  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  29.  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  30.  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  31.  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  32.  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  33.  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  34.  * SUCH DAMAGE.
  35.  */
  36.  
  37. #if defined(LIBC_SCCS) && !defined(lint)
  38. static char sccsid[] = "@(#)bt_put.c    8.1 (Berkeley) 6/4/93";
  39. #endif /* LIBC_SCCS and not lint */
  40.  
  41. #include <sys/types.h>
  42.  
  43. #include <errno.h>
  44. #include <stdio.h>
  45. #include <stdlib.h>
  46. #include <string.h>
  47.  
  48. #include <db.h>
  49. #include "btree.h"
  50.  
  51. static EPG *bt_fast __P((BTREE *, const DBT *, const DBT *, int *));
  52.  
  53. /*
  54.  * __BT_PUT -- Add a btree item to the tree.
  55.  *
  56.  * Parameters:
  57.  *    dbp:    pointer to access method
  58.  *    key:    key
  59.  *    data:    data
  60.  *    flag:    R_NOOVERWRITE
  61.  *
  62.  * Returns:
  63.  *    RET_ERROR, RET_SUCCESS and RET_SPECIAL if the key is already in the
  64.  *    tree and R_NOOVERWRITE specified.
  65.  */
  66. int
  67. __bt_put(dbp, key, data, flags)
  68.     const DB *dbp;
  69.     DBT *key;
  70.     const DBT *data;
  71.     u_int flags;
  72. {
  73.     BTREE *t;
  74.     DBT tkey, tdata;
  75.     EPG *e;
  76.     PAGE *h;
  77.     indx_t index, nxtindex;
  78.     pgno_t pg;
  79.     size_t nbytes;
  80.     int dflags, exact, status;
  81.     char *dest, db[NOVFLSIZE], kb[NOVFLSIZE];
  82.  
  83.     t = dbp->internal;
  84.  
  85.     switch (flags) {
  86.     case R_CURSOR:
  87.         if (!ISSET(t, B_SEQINIT))
  88.             goto einval;
  89.         if (ISSET(t, B_DELCRSR))
  90.             goto einval;
  91.         break;
  92.     case 0:
  93.     case R_NOOVERWRITE:
  94.         break;
  95.     default:
  96. einval:        errno = EINVAL;
  97.         return (RET_ERROR);
  98.     }
  99.  
  100.     if (ISSET(t, B_RDONLY)) {
  101.         errno = EPERM;
  102.         return (RET_ERROR);
  103.     }
  104.  
  105.     /*
  106.      * If the key/data won't fit on a page, store it on indirect pages.
  107.      * Only store the key on the overflow page if it's too big after the
  108.      * data is on an overflow page.
  109.      *
  110.      * XXX
  111.      * If the insert fails later on, these pages aren't recovered.
  112.      */
  113.     dflags = 0;
  114.     if (key->size + data->size > t->bt_ovflsize) {
  115.         if (key->size > t->bt_ovflsize) {
  116. storekey:        if (__ovfl_put(t, key, &pg) == RET_ERROR)
  117.                 return (RET_ERROR);
  118.             tkey.data = kb;
  119.             tkey.size = NOVFLSIZE;
  120.             memmove(kb, &pg, sizeof(pgno_t));
  121.             memmove(kb + sizeof(pgno_t),
  122.                 &key->size, sizeof(size_t));
  123.             dflags |= P_BIGKEY;
  124.             key = &tkey;
  125.         }
  126.         if (key->size + data->size > t->bt_ovflsize) {
  127.             if (__ovfl_put(t, data, &pg) == RET_ERROR)
  128.                 return (RET_ERROR);
  129.             tdata.data = db;
  130.             tdata.size = NOVFLSIZE;
  131.             memmove(db, &pg, sizeof(pgno_t));
  132.             memmove(db + sizeof(pgno_t),
  133.                 &data->size, sizeof(size_t));
  134.             dflags |= P_BIGDATA;
  135.             data = &tdata;
  136.         }
  137.         if (key->size + data->size > t->bt_ovflsize)
  138.             goto storekey;
  139.     }
  140.  
  141.     /* Replace the cursor. */
  142.     if (flags == R_CURSOR) {
  143.         if ((h = mpool_get(t->bt_mp, t->bt_bcursor.pgno, 0)) == NULL)
  144.             return (RET_ERROR);
  145.         index = t->bt_bcursor.index;
  146.         goto delete;
  147.     }
  148.  
  149.     /*
  150.      * Find the key to delete, or, the location at which to insert.  Bt_fast
  151.      * and __bt_search pin the returned page.
  152.      */
  153.     if (t->bt_order == NOT || (e = bt_fast(t, key, data, &exact)) == NULL)
  154.         if ((e = __bt_search(t, key, &exact)) == NULL)
  155.             return (RET_ERROR);
  156.     h = e->page;
  157.     index = e->index;
  158.  
  159.     /*
  160.      * Add the specified key/data pair to the tree.  If an identical key
  161.      * is already in the tree, and R_NOOVERWRITE is set, an error is
  162.      * returned.  If R_NOOVERWRITE is not set, the key is either added (if
  163.      * duplicates are permitted) or an error is returned.
  164.      *
  165.      * Pages are split as required.
  166.      */
  167.     switch (flags) {
  168.     case R_NOOVERWRITE:
  169.         if (!exact)
  170.             break;
  171.         /*
  172.          * One special case is if the cursor references the record and
  173.          * it's been flagged for deletion.  Then, we delete the record,
  174.          * leaving the cursor there -- this means that the inserted
  175.          * record will not be seen in a cursor scan.
  176.          */
  177.         if (ISSET(t, B_DELCRSR) && t->bt_bcursor.pgno == h->pgno &&
  178.             t->bt_bcursor.index == index) {
  179.             CLR(t, B_DELCRSR);
  180.             goto delete;
  181.         }
  182.         mpool_put(t->bt_mp, h, 0);
  183.         return (RET_SPECIAL);
  184.     default:
  185.         if (!exact || !ISSET(t, B_NODUPS))
  186.             break;
  187. delete:        if (__bt_dleaf(t, h, index) == RET_ERROR) {
  188.             mpool_put(t->bt_mp, h, 0);
  189.             return (RET_ERROR);
  190.         }
  191.         break;
  192.     }
  193.  
  194.     /*
  195.      * If not enough room, or the user has put a ceiling on the number of
  196.      * keys permitted in the page, split the page.  The split code will
  197.      * insert the key and data and unpin the current page.  If inserting
  198.      * into the offset array, shift the pointers up.
  199.      */
  200.     nbytes = NBLEAFDBT(key->size, data->size);
  201.     if (h->upper - h->lower < nbytes + sizeof(indx_t)) {
  202.         if ((status = __bt_split(t, h, key,
  203.             data, dflags, nbytes, index)) != RET_SUCCESS)
  204.             return (status);
  205.         goto success;
  206.     }
  207.  
  208.     if (index < (nxtindex = NEXTINDEX(h)))
  209.         memmove(h->linp + index + 1, h->linp + index,
  210.             (nxtindex - index) * sizeof(indx_t));
  211.     h->lower += sizeof(indx_t);
  212.  
  213.     h->linp[index] = h->upper -= nbytes;
  214.     dest = (char *)h + h->upper;
  215.     WR_BLEAF(dest, key, data, dflags);
  216.  
  217.     if (t->bt_order == NOT)
  218.         if (h->nextpg == P_INVALID) {
  219.             if (index == NEXTINDEX(h) - 1) {
  220.                 t->bt_order = FORWARD;
  221.                 t->bt_last.index = index;
  222.                 t->bt_last.pgno = h->pgno;
  223.             }
  224.         } else if (h->prevpg == P_INVALID) {
  225.             if (index == 0) {
  226.                 t->bt_order = BACK;
  227.                 t->bt_last.index = 0;
  228.                 t->bt_last.pgno = h->pgno;
  229.             }
  230.         }
  231.  
  232.     mpool_put(t->bt_mp, h, MPOOL_DIRTY);
  233.  
  234. success:
  235.     if (flags == R_SETCURSOR) {
  236.         t->bt_bcursor.pgno = e->page->pgno;
  237.         t->bt_bcursor.index = e->index;
  238.     }
  239.     SET(t, B_MODIFIED);
  240.     return (RET_SUCCESS);
  241. }
  242.  
  243. #ifdef STATISTICS
  244. u_long bt_cache_hit, bt_cache_miss;
  245. #endif
  246.  
  247. /*
  248.  * BT_FAST -- Do a quick check for sorted data.
  249.  *
  250.  * Parameters:
  251.  *    t:    tree
  252.  *    key:    key to insert
  253.  *
  254.  * Returns:
  255.  *     EPG for new record or NULL if not found.
  256.  */
  257. static EPG *
  258. bt_fast(t, key, data, exactp)
  259.     BTREE *t;
  260.     const DBT *key, *data;
  261.     int *exactp;
  262. {
  263.     EPG e;
  264.     PAGE *h;
  265.     size_t nbytes;
  266.     int cmp;
  267.  
  268.     if ((h = mpool_get(t->bt_mp, t->bt_last.pgno, 0)) == NULL) {
  269.         t->bt_order = NOT;
  270.         return (NULL);
  271.     }
  272.     e.page = h;
  273.     e.index = t->bt_last.index;
  274.  
  275.     /*
  276.      * If won't fit in this page or have too many keys in this page, have
  277.      * to search to get split stack.
  278.      */
  279.     nbytes = NBLEAFDBT(key->size, data->size);
  280.     if (h->upper - h->lower < nbytes + sizeof(indx_t))
  281.         goto miss;
  282.  
  283.     if (t->bt_order == FORWARD) {
  284.         if (e.page->nextpg != P_INVALID)
  285.             goto miss;
  286.         if (e.index != NEXTINDEX(h) - 1)
  287.             goto miss;
  288.         if ((cmp = __bt_cmp(t, key, &e)) < 0)
  289.             goto miss;
  290.         t->bt_last.index = cmp ? ++e.index : e.index;
  291.     } else {
  292.         if (e.page->prevpg != P_INVALID)
  293.             goto miss;
  294.         if (e.index != 0)
  295.             goto miss;
  296.         if ((cmp = __bt_cmp(t, key, &e)) > 0)
  297.             goto miss;
  298.         t->bt_last.index = 0;
  299.     }
  300.     *exactp = cmp == 0;
  301. #ifdef STATISTICS
  302.     ++bt_cache_hit;
  303. #endif
  304.     return (&e);
  305.  
  306. miss:
  307. #ifdef STATISTICS
  308.     ++bt_cache_miss;
  309. #endif
  310.     t->bt_order = NOT;
  311.     mpool_put(t->bt_mp, h, 0);
  312.     return (NULL);
  313. }
  314.